package tree;

import java.util.*;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/9/25
 */
public class BinaryTreeUtil {

    public static TreeNode buildTree(int []arr) {
        return buildTree(arr,0);
    }

    public static TreeNode buildTree(int[] arr,int index) {
        if (index >= arr.length || arr[index] == -1) {
            return null;
        }
        TreeNode root = new TreeNode(arr[index]);
        root.left = buildTree(arr,2*index+1);
        root.right = buildTree(arr,2*index+2);
        return root;
    }

    public interface Traversal {

        /**
         * 层序遍历
         * @param root
         */
        static void sequenceTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode curr = queue.poll();
                System.out.print(curr.element + " ");
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
        }

        /**
         * 先序遍历
         * @param root
         */
        void preorderTraversal(TreeNode root);

        /**
         * 中序遍历
         * @param root
         */
        void inorderTraversal(TreeNode root);

        /**
         * 后续遍历
         * @param root
         */
        void postorderTraversal(TreeNode root);
    }

    /**
     * 递归遍历
     */
    public static class RecursiveTraversal implements Traversal {


        @Override
        public void preorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            System.out.print(root.element + " ");
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }

        @Override
        public void inorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            inorderTraversal(root.left);
            System.out.print(root.element+" ");
            inorderTraversal(root.right);
        }

        @Override
        public void postorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.element + " ");
        }
    }

    /**
     * 迭代遍历
     */
    public static class IterativeTraversal implements Traversal {


        @Override
        public void preorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curr = root;

            while (!stack.isEmpty() || curr != null) {
                if (curr != null) {
                    stack.push(curr);
                    System.out.print(curr.element + " ");
                    curr = curr.left;
                } else {
                    curr = stack.pop();
                    curr = curr.right;
                }
            }
        }

        @Override
        public void inorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curr = root;

            while (!stack.isEmpty() || curr != null) {
                if (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                } else {
                    curr = stack.pop();
                    System.out.print(curr.element + " ");
                    curr = curr.right;
                }
            }
        }

        @Override
        public void postorderTraversal(TreeNode root) {
            postOrder1(root);
        }

        /**
         * 按照根右左的顺序实现，将存储的结果翻转
         * @param root
         */
        private void postOrder1(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            List<TreeNode> list = new ArrayList<>();
            TreeNode curr = root;
            while (curr!=null|| !stack.isEmpty()) {
                if (curr != null) {
                    stack.push(curr);
                    list.add(curr);
                    curr = curr.right;
                } else {
                    curr = stack.pop();
                    curr = curr.left;
                }
            }
            Collections.reverse(list);
            list.stream()
                    .map(TreeNode::getElement)
                    .map(e -> e + " ")
                    .forEach(System.out::print);
        }
    }
}
